package main

import "fmt"

//循环二分查找:16ms 95%,6.5MB 58%
func findNumberIn2DArray(matrix [][]int, target int) bool {
	for _, v := range matrix {
		l, r := 0, len(v)-1
		for l <= r {
			m := (l + r) / 2
			if v[m] == target {
				return true
			}
			if v[m] > target {
				r = m - 1
			} else {
				l = m + 1
			}
		}
	}
	return false
}

//左下角逐行消减:16ms 95%,6.5MB 58%
func findNumberIn2DArray1(matrix [][]int, target int) bool {
	n, m := len(matrix)-1, 0
	for n >= 0 && m < len(matrix[0]) {
		if matrix[n][m] == target {
			return true
		} else if matrix[n][m] > target {
			n--
		} else {
			m++
		}
	}
	return false
}

func main() {
	fmt.Println(findNumberIn2DArray([][]int{{0}}, 0))
	fmt.Println(findNumberIn2DArray1([][]int{{0}}, 0))
}
